1. Field of the Invention
The present invention relates generally to databases and, more specifically, to parallel processing of data from databases.
2. Description of the Background Art
Database products are commonly written to be able to handle sets of data that far exceed the available memory. This is typically accomplished through the use of “disk sort” or “external sort” algorithms. In a disk sort, arriving data is packaged as records and then placed into a set of pages. When the set of pages reaches some memory limit, the data is sorted, resulting in a “sort run”. This sort run is then released from cache and allowed to page to disk, so a new sort run can be created using additional data. Data is read out from several sort runs using one of several techniques in a merging process. This allows data from two or more sort runs to be read out in sorted order.
As the volume of data processed using sort runs and other database techniques increases, a common solution to improve performance is to increase hardware capacity. One area where significant capacity increases have been seen lately is in multi-core/multi-processor systems. However, in order to effectively use this capacity in a database product, the database must be able to efficiently enable queries to simultaneously use multiple cores or multiple processors to operate on data.
Query parallelism is commonly enabled by dividing the data to be processed into disjoint subsets, and then applying query operators on each of the subsets simultaneously on parallel execution threads. However, this data division commonly relies on a database administrator to specify the division points, and likely based only on one or two sets of key columns, and with only a few division points potentially resulting in large data sets. The decision to specify division points must also be made at latest at query optimization time, with no ability to correct for uneven distribution of rows among the disjoint sets.
Additional efforts to parallelize these disk sort techniques for database use have also primarily focused on parallelization within the sort operation itself. These techniques include placing the insertion of records into sort runs on separate threads of execution from the sorting of records within a sort run, parallelization of comparison operations within a champion tree being used during the merging process, and having multiple threads inserting records concurrently into separate sort runs.
Few efforts have concentrated on parallelization of the operations that are dependent on the results of the disk sort. The predominant technique is the use of key-based binning, where records are separated into two or more “bins” based on a range of key values. Sets of sort runs corresponding to a same bin, having key values corresponding to the range of key values, can then be merged for read out using existing techniques, such as champion trees. However, binning suffers from an inability to adapt to circumstances, including the contents of the sort and processing resources.
Accordingly, what is desired are techniques to improve parallelization of data sets held in sort runs.